package alogrithm;

import java.util.Arrays;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/9/9 20:59
 */
public class MergeSort {
    static int[] aux;

    public static void main(String[] args) {
        int[] a = new int[]{1, 7, 5, 6, 4, 2, 3};
        int n = a.length;
        aux = new int[n];
        // sort(a, 0, n - 1);
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    // 自顶向下的归并排序
    private static void sort(int[] a, int low, int high) {
        if (high <= low) return;
        int mid = low + (high - low) / 2;
        sort(a, low, mid);
        sort(a, mid + 1, high);
        mergeSort(a, low, mid, high);
    }

    // 自底向上的归并排序
    private static void sort(int[] a) {
        int n = a.length;
        aux = new int[n];
        for (int sz = 1; sz < n; sz += sz) {
            for (int low = 0; low < n - sz; low += sz + sz) {
                mergeSort(a, low, low + sz - 1, Math.min(low + sz + sz - 1, n - 1));

            }
        }
    }

    private static void mergeSort(int[] a, int low, int mid, int high) {
        int i = low, j = mid + 1;
        // System.arraycopy(a, 0, aux, 0, high + 1);
        for (int k = low; k <= high; k++) {
            aux[k] = a[k];
        }
        for (int k = low; k <= high; ++k) {
            // i > mid 代表左边元素已经用完
            if (i > mid) a[k] = aux[j++];
            else if (j > high) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }

    }
}
